package com.lun.swordtowardoffer2.c11;

import java.util.Random;

public class PickIndex {

	private int[] nums;
	private int total;
	
	public PickIndex(int[] nums) {
		this.total = 0;
		this.nums = new int[nums.length];
		for(int i = 0; i < nums.length; i++) {
			this.total += nums[i];
			this.nums[i] = this.total;
		}
	}
	
	public int pickIndex() {
		Random rand = new Random(System.nanoTime());
		int randInt = rand.nextInt(total);
		
		int left = 0, right = nums.length - 1;
		
		while(left <= right) {
			int mid = left + (right - left) / 2;
						
			if(randInt < nums [mid]) {
				if(mid == 0 || nums[mid - 1] <= randInt) {
					return mid;
				}
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}
		return -1;
	}
	
}
